package difficult.dp;

import java.util.Arrays;

/**
 * 354. 俄罗斯套娃信封问题
 * 给定一些标记了宽度和高度的信封，宽度和高度以整数对形式(w, h)出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
 * 请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
 * 说明: 不允许旋转信封。
 * 示例:
 *   输入: envelopes = [[5,4],[6,4],[6,7],[2,3]]
 *   输出: 3
 *   解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
 * @author 刘学松
 * @date 2021/3/4 12:39
 */
public class 俄罗斯套娃信封问题 {
    public static void main(String[] args) {
//        int[][] envelopes = {{5,4}, {6,4}, {6,7}, {2,3}};
//        int[][] envelopes = {{1,1}, {1,1}, {1,1}, {1,1}};
//        int[][] envelopes = {{4,5}, {4,6}, {6,7}, {2,3}, {1,1}};
        int[][] envelopes = {{1,2}, {2,3}, {3,4}, {4,5}, {5,6}, {5,5}, {6,7}, {7,8}};
        System.out.println(maxEnvelopes(envelopes));
    }


    public static int maxEnvelopes(int[][] envelopes) {
        int length = envelopes.length;
        if (length < 2) {
            return length;
        }
        Arrays.sort(envelopes, (x, y) -> x[0] != y[0] ? x[0]-y[0] : x[1]-y[1]);
        int[] counts = new int[length];
        Arrays.fill(counts, 1);
        int max = 1;
        for (int i = 1; i < length; i++) {
            for (int j = 0; j < i; j++) {
                if (envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]) {
                    counts[i] = Math.max(counts[i], counts[j]+1);
                }
            }
            max = Math.max(max, counts[i]);
        }
        return max;
    }
}
